
\subsection{Problem 4}

Mandatory (5): Add loop bounds and additional flow facts for insertion sort.c:insertion sort(), using the symbolic name @size for the size of the array to be sorted. Next, analyze the WCET of insertion sort, assuming an array size of 32. Keep the array size as a symbolic name (user register @size). Finally, write a test function which calls insertion sort more than once, with different array sizes (e.g., 16,32 and 64). Also repeat the static analysis with different array sizes.
\\
Q: How many cycles do you need to execute insertion sort according to the static analysis? 
\\
Q: What results do you get for an array size of 8,16 or 64, using measurements and static analysis? 
\\
Q: In addition to the size of the array, what other aspects of the input data might influence the WCET?
\\
\\
\textbf{Solution:}
\\
\\
A comparison of the results of the static analysis and the results of the software measurements with different array input sizes can be found in Table~\ref{tab:4}. The file \texttt{insertion\_sort.c} with its annotations for \textit{aiT} for the static analysis is listed in Section~\ref{sec:insertion}. The assembler annotation are listed in Section~\ref{sec:ins_ais}. The 4 figures below show the results of the static
analysis with \textit{aiT} (we forgot to make new pictures after we added the assembler annotations, this are the old pictures, the new values are in Table~\ref{tab:4}).

\noindent The preexisting ordering of input elements does have an influence to the execution time (an ascending preordered input set results in much less loop iterations), but it does not influence the WCET, which needs to account the maximum execution time.

\noindent The last column of Table~\ref{tab:4} shows our chosen flow constraints for the inner while loop. For the arrays with 8 and 16 elements the WCET is higher than the time measured on the hardware. But the WCET for the 32 and 64 element array is less than the measured value. We inspected the output of the \textit{aiT} and could not find any error. We think the flow constraints are right.

\begin{table}
\centering
	\begin{tabular}[!htpb]{|c|c|c|c|c|} 
		\hline
		size of input array	& Static analysis (cycles) & SW measurement (cycles) & flow constraints\\
		\hline
		\hline
		8 	& 3533 & 3271 & 28\\
		16 	& 12421 & 12171 & 120\\
		32 	& 45941 & 47059 & 496\\
		64	& 175957 & 185199 & 2016\\
		\hline
	\end{tabular} 
	\caption{Results of the static analysis and software measurements for \texttt{insertion sort} with different array input sizes \label{tab:4}}
\end{table}  

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.40\textwidth]{figures/4_8.PNG}
	\caption{Static analysis of \texttt{insertion\_sort} with array size 8}
	\label{fig:4_8}
\end{figure}

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.40\textwidth]{figures/4_16.PNG}
		\caption{Static analysis of \texttt{insertion\_sort} with array size 16}
	\label{fig:4_16}
\end{figure}

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.40\textwidth]{figures/4_32.PNG}
		\caption{Static analysis of \texttt{insertion\_sort} with array size 32}
	\label{fig:4_32}
\end{figure}

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.40\textwidth]{figures/4_64.PNG}
		\caption{Static analysis of \texttt{insertion\_sort} with array size 64}
	\label{fig:4_64}
\end{figure}
